Recursion Lists II (map) Lists III (folds, comprehensions) Type declarations Pattern matching Control structures More on functions Higher-order functions Using GHCi effectively

At the heart of functional programming is the idea that functions are just like any other value. The power of functional style comes from handling functions themselves as regular values, i.e. by passing functions to other functions and returning them from functions. A function that takes another function (or several functions) as an argument is called a higher-order function. They can be found pretty much anywhere in a Haskell program, and indeed we have already met some of them, such as map and the various folds. We saw commonplace examples of higher-order functions when discussing map in Lists II. Now, we are going to explore some common ways of writing code that manipulates functions.

For a concrete example, we will consider the task of sorting a list. Quicksort is a well-known recursive sorting algorithm. To apply its sorting strategy to a list, we first choose one element and then divide the rest of the list into (A) those elements that should go before the chosen element, (B) those elements equal to the chosen one, and (C) those that should go after. Then, we apply the same algorithm to the unsorted (A) and (C) lists. After enough recursive sorting, we concatenate everything back together and have a final sorted list. That strategy can be translated into a Haskell implementation in a very simple way.

It should be pointed out that our quickSort is rather naïve. A more efficient implementation would avoid the three passes through filter at each recursive step and not use (++) to build the sorted list. Furthermore, unlike our implementation, the original quicksort algorithm does the sorting in-place using mutability.[1] We will ignore such concerns for now, as we are more interested in the usage patterns of sorting functions, rather than in exact implementation.

Almost all the basic data types in Haskell are members of the Ord class, which is for ordering tests what Eq is for equality tests. The Ord class defines which ordering is the "natural" one for a given type. It provides a function called compare, with type:

compare takes two values and compares them, returning an Ordering value, which is LT if the first value is less than the second, EQ if it is equal and GT if it is greater than. For an Ord type, () can be seen as shortcuts to compare that check for one of the three possibilities and return a Bool to indicate whether the specified ordering is true according to the Ord specification for that type. Note that each of the tests we use with filter in the definition of quickSort corresponds to one of the possible results of compare, and so we might have written, for instance, less as less = filter (\y -> y `compare` x == LT) xs.

With quickSort, sorting any list with elements in the Ord class is easy. Suppose we have a list of String and we want to sort them; we just apply quickSort to the list. For the rest of this chapter, we will use a pseudo-dictionary of just a few words (but dictionaries with thousands of words would work just as well):

quickSort dictionary returns:

As you can see, capitalization is considered for sorting by default. Haskell Strings are lists of Unicode characters. Unicode (and almost all other encodings of characters) specifies that the character code for capital letters are less than the lower case letters. So "Z" is less than "a".

To get a proper dictionary-like sorting, we need a case insensitive quickSort. To achieve that, we can take a hint from the discussion of compare just above. The recursive case of quickSort can be rewritten as:

While this version is less tidy than the original one, it makes it obvious that the ordering of the elements hinges entirely on the compare function. That means we only need to replace compare with an (Ord a) => a -> a -> Ordering function of our choice. Therefore, our updated quickSort' is a higher-order function which takes a comparison function along with the list to sort.

We can reuse our quickSort' function to serve many different purposes.

If we wanted a descending order, we could just reverse our original sorted list with reverse (quickSort dictionary). Yet to actually do the initial sort descending, we could supply quickSort' with a comparison function that returns the opposite of the usual Ordering.

Note

Data.List offers a sort function for sorting lists. It does not use quicksort; rather, it uses an efficient implementation of an algorithm called mergesort. Data.List also includes sortBy, which takes a custom comparison function just like our quickSort'

The concept of currying (the generating of intermediate functions on the way toward a final result) was first introduced in the earlier chapter "Lists II". This is a good place to revisit how currying works.

Our quickSort' has type (a -> a -> Ordering) -> [a] -> [a].

Most of the time, the type of a higher-order function provides a guideline about how to use it. A straightforward way of reading the type signature would be "quickSort' takes, as its first argument, a function that gives an ordering of two as. Its second argument is a list of as. Finally, it returns a new list of as". This is enough to correctly guess that it uses the given ordering function to sort the list.

Note that the parentheses surrounding a -> a -> Ordering are mandatory. They specify that a -> a -> Ordering forms a single argument that happens to be a function.

Without the parentheses, we would get a -> a -> Ordering -> [a] -> [a] which accepts four arguments (none of which are themselves functions) instead of the desired two, and that wouldn't work as desired.

Remember that the -> operator is right-associative. Thus, our erroneous type signature a -> a -> Ordering -> [a] -> [a] means the same thing as a -> (a -> (Ordering -> ([a] -> [a]))).

Given that -> is right-associative, the explicitly grouped version of the correct quickSort' signature is actually (a -> a -> Ordering) -> ([a] -> [a]). This makes perfect sense. Our original quickSort lacking the adjustable comparison function argument was of type [a] -> [a]. It took a list and sorted it. Our new quickSort' is simply a function that generates quickSort style functions! If we plug in compare for the (a -> a -> Ordering) part, then we just return our original simple quickSort function. If we use a different comparison function for the argument, we generate a different variety of a quickSort function.

Of course, if we not only give a comparison function as an argument but also feed in an actual list to sort, then the final result is not the new quickSort-style function; instead, it continues on and passes the list to the new function and returns the sorted list as our final result.

(Challenging) The following exercise combines what you have learned about higher order functions, recursion and I/O. We are going to recreate what is known in imperative languages as a for loop. Implement a function

An example of how this function would be used might be

Haskell Basics >> Elementary Haskell >> Intermediate Haskell >> Monads Advanced Haskell >> Fun with Types >> Wider Theory >> Haskell Performance

Libraries Reference >> General Practices >> Specialised Tasks